import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-11-09
 * Time: 11:46
 */
public class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        //判断长度是否合理
        if (n%2 == 1) {
            return false;
        }

        //如果遇到左括号就放到栈中，遇到右括号就进行比较
        Stack<Character> stack = new Stack<>();

        //用HashMap记录匹配关系
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                if (stack.empty() || stack.peek() != map.get(ch)) {
                    return false;
                }
                stack.pop();
            }else {
                stack.push(ch);
            }
        }



        /*for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else if (!stack.empty()){
                char sh = stack.peek();
                if (ch == ')' && sh == '(') {
                    stack.pop();
                }
                else if (ch == ']' && sh == '[') {
                    stack.pop();
                }
                else if (ch == '}' && sh == '{') {
                    stack.pop();
                }else {
                    return false;
                }
            }else {
                return false;
            }
        }*/

        return stack.empty();
    }
}
